package 剑指offer.demo5;

import java.util.ArrayList;

//https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?
/*
字符串转换成数组（方便操作）递归交换处理，每个字符串判断是否加入列表，一定注意理解递归过程
 */
public class 字符串的排列 {
    public ArrayList<String> Permutation (String str) {
        //创建ArrayList用于返回
        ArrayList<String> result = new ArrayList<>();
        //有正确str进行操作
        if (str.length() > 0 && str != null){
            help(str.toCharArray() , 0 , result);
        }
        return result;
    }
    //字符串数组方便操作,把原字符串转换为数组，给定数组，开始位置，添加在ArrayList
    public void help(char[] arr , int start , ArrayList<String> list){
        if (start == arr.length - 1){
            //list不包含的话把arr添加进去
            if (!list.contains(String.valueOf(arr))){
                list.add(String.valueOf(arr));
            }
            return;
        }
        //这里别犯傻逼，arr就是str转换的字符数组
        for (int i = start; i < arr.length; i++) {
            swap(arr , i , start);
            help(arr , start + 1 , list);
            //记得操作完之后交换回来方便下次操作
            swap(arr , i , start);
        }
    }
    //交换数组i、j下标索引
    public void swap(char[] arr , int i , int j){
        char cur = arr[i];
        arr[i] = arr[j];
        arr[j] = cur;
    }
}
